import java.util.*;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
public class project {
    public int longestConsecutive(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        Arrays.sort(nums);
        int max=1;
        int count=1;
        for(int i=nums.length-1;i>0;i--){
            if(nums[i]-nums[i-1]==1){
                count++;
            }else if(nums[i]-nums[i-1]==0){

            }else{
                count=1;
            }
            max=Math.max(count,max);
        }
        return max;
    }















    public Node connect(Node root) {
        Queue<Node> queue=new LinkedList<>();
        if(root!=null){
            queue.offer(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                for(int i=0;i<size;i++){
                    Node tmp=queue.poll();
                    if(i==size-1){
                        tmp.next=null;
                    }else{
                        tmp.next=queue.peek();
                    }
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.add(tmp.right);
                    }
                }
            }
        }
        return root;
    }










    public int countValidWords(String sentence) {
        String[] str=sentence.split(" ");
        int ans=0;
        for(String s : str){
            char[] ch=s.toCharArray();
            int len=ch.length;
            if(len==0){
                continue;
            }
            if(ch[0]=='-'||ch[len-1]=='-'){
                continue;
            }
            boolean bool=false;
            int count=0;
            for(int i=0;i<len;i++){
                if(ch[i]>='0'&&ch[i]<='9'){
                    bool=true;
                    break;
                }
                if((ch[i]=='!'||ch[i]==','||ch[i]=='.')&&i!=len-1){
                    bool=true;
                    break;
                }
                if(ch[i]=='-'){
                    count++;
                    if(count>1){
                        bool=true;
                        break;
                    }
                    if(ch[i-1]<'a'||ch[i-1]>'z'||ch[i+1]<'a'||ch[i+1]>'z'){
                        bool=true;
                        break;
                    }
                }
            }
            if(!bool){
                ans++;
            }
        }
        return ans;
    }













    public boolean canPartition(int[] nums) {
        int len=nums.length;
        if(len<1){
            return false;
        }
        int count=0;
        for(int i=0;i<nums.length;i++){
            count+=nums[i];
        }
        if(count%2==1){
            return false;
        }
        int target=count/2;
        boolean[] bool=new boolean[target+1];
        bool[0]=true;
        for(int i=0;i<len;i++){
            int tmp=nums[i];
            for(int j=target;j>tmp-1;j--){
                int t=j-tmp;
                if(bool[t]==true){
                    bool[j]=true;
                }
            }
        }
        return  bool[target];
    }








    public int divide(int a, int b) {
        if(a==Integer.MIN_VALUE&&b==-1){
            return Integer.MAX_VALUE;
        }
        int sign=(a>0)^(b>0)?-1:1;
        if(a>0){
            a=-a;
        }
        if(b>0){
            b=-b;
        }
        int res=0;
        while(a<=b){
            a-=b;
            res++;
        }
        return sign==1?res:-res;
    }













    public int countVowelSubstrings(String word) {
        String s="aeiou";
        int sum=0;
        for(int i=0;i<word.length();i++){
            Set<Character> set=new HashSet<>();
            for(int j=i;j<word.length();j++){
                if(s.contains("" + word.charAt(j))){
                    set.add(word.charAt(j));
                    if(set.size()==5){
                        sum++;
                    }
                } else{
                    break;
                }
            }
        }
        return sum;
    }








    public int smallestEqual(int[] nums) {
        int index=-1;
        for(int i=0;i<nums.length;i++){
            if(i%10==nums[i]){
                return i;
            }
        }
        return -1;
    }












    public int countQuadruplets(int[] nums) {
        int count=0;
        for(int i=0;i<nums.length-3;i++){
            for(int j=i+1;j<nums.length-2;j++){
                for(int k=j+1;k<nums.length-1;k++){
                    for(int p=k+1;p<nums.length;p++){
                        if((nums[i]+nums[j]+nums[k])==nums[p]){
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }








    public int minimumMoves(String s) {
        int count=0;
        int i=0;
        while(i<s.length()){
            if(s.charAt(i)=='X'){
                i+=2;
                count++;
            }
            i++;
        }
        return count;
    }









    public int maximumDifference(int[] nums) {
        int max=-1;
        for(int i=nums.length-1;i>0;i--){
            for(int j=i-1;j>=0;j--){
                if(nums[i]>nums[j]){
                    max=Math.max(max,nums[i]-nums[j]);
                }
            }
        }
        return max;
    }
}
